A Physical Uncloneable Function (PUF) is a function which is embodied as a physical system, in such a way that an output of the function for an input is obtained by offering the input to the physical system in the form of a stimulus, and mapping the behavior that occurs as a result of an interaction between the stimulus and the physical system to an output. Wherein the interaction is unpredictable and depends on essentially random elements in the physical system, to such an extent, that it is unfeasible to obtain the output, without having had physical access to the physical system, and that it is unfeasible to reproduce the physical system. Preferably, a PUF is also easy to evaluate. For practical uses, PUFs are preferably low in manufacture costs.
Conventionally, an input or stimulus that a PUF accepts is called a ‘challenge’. The output of a PUF, that is, the behavior the PUF exhibits after interaction with the stimulus, is called a ‘response’. A pair comprising a challenge and the corresponding response of a PUF is called a challenge-response pair. Some types of PUFs allow a wide range of different inputs, some types allow a more limited range of inputs, or may even allow only a single input. It would be most preferable, if a PUF when evaluated multiple times for the same challenge would produce multiple responses which are all equal. This property is not necessary though, and, in practice, most PUFs do not posses it. As long as the multiple responses lie sufficiently close to each other, the PUF can be usefully applied.
Since the interaction between a stimulus and the physical system cannot be predicted without access to the system, the PUF is hard to characterize and to model. The output of a particular PUF for an input can therefore only be obtained using the particular physical system underlying the particular PUF. Possession of a challenge-response pair is proof that at some point the challenge was offered to the unique physical system that underlies the PUF. Because of this property, i.e., the property that challenge-response pairs are coupled to a unique physical device, a PUF is called uncloneable. By equipping a device with a PUF, the device also becomes uncloneable.
Physical systems that are produced by a production process that is, at least in part, uncontrollable, i.e., a production process which will inevitably introduce some randomness, turn out to be good candidates for PUFs.
One advantage of PUFs is that they inherently possess tamper resistant qualities: disassembling the PUF to observe its working, will also disturb the random elements and therefore also disturb the way inputs are mapped to outputs. Various types of PUFs are known in the art, including optical PUFs and electronical PUFs.
One way of constructing a PUF uses a static random access memory (SRAM); these PUFs are called SRAM PUFs. SRAMs have the property that after they are powered-up, they are filled with a random pattern of on-bits and off-bits. Although the pattern may not repeat itself exactly if the SRAM is powered-up a next time, the differences between two such patterns is typically much smaller than half the number of bits in the state.
A second kind of S-RAM PUFs is constructed with Dual Port RAM. By writing at the same time different information on both ports, the memory cell is brought into an undefined state which shows a PUF-like behavior.
Due to unavoidable variations during production, the configuration of the components of an SRAM relative to each other is at least slightly random. These variations are reflected, e.g., in a slightly different threshold voltage of the memory cells of the SRAM. When the SRAM is read out in an undefined state, e.g., before a write action, the output of the SRAM depends on the random configuration. Producing a new SRAM, with the same characteristic behavior requires producing an SRAM with the same configuration, a configuration which was achieved randomly. As this is unfeasible, the SRAM is uncloneable as a physical system, that is, it is a PUF.
A further example of PUFs are the so-called delay PUFs. The delay caused by a connection between two regions of an integrated circuit, such as an FPGA, is precisely measured and used for the PUF output. The delay may, e.g., be measured by incorporating the connection in a ring oscillator and determining the frequency of the ring oscillator. The connection may be routed depending on an input of the PUF. For example, the connection may be routed through a series of delay elements, wherein each delay element comprises at least two possible paths. The input to the PUF comprises multiple selector bits, the path used in a specific delay element depending on a specific selector bit. Since the components in the delay elements differ at least slightly, the precise delay which is caused by a delay element also differs slightly. Accordingly, the output of the delay PUF depends on the random configuration of the components.
Note that some pre or post processing may be used with a PUF. For example, a delay PUF may be used multiple times to produce multiple output bits, which are concatenated together to produce a bit-string. Also a PUF may use processing data to aid the processing of the PUF. For example, average delay times may be stored with a delay PUF in order to compare the actual delay with an average delay.
One application of PUFs is to derive a cryptographic key on an electronic circuit. The electronic circuit typically includes an integrated Circuit (IC) and/or programmable logic. The programmable logic comprises, e.g., a field-programmable gate array (FPGA), a programmable logic device (PLD), or a digital signal processor (DSP), a microprocessor, etc. Instead of storing the cryptographic key in a non-volatile memory of some kind, the key is generated from the PUF only when the key is needed by the device. The key can be deleted when it is no longer needed. The next time the key is needed, it can be derived again from the PUF. Since the PUF may not give the exact same result when the same challenge is evaluated twice, a so-called Helper Data algorithm, also known as a Fuzzy Extractor, may be used to ensure that the key will be the same, each time it is derived. One way of using helper data to construct reproducible values from noisy measurements is described, e.g., in international patent application WO 2006/129242, “Template Renewal in Helper Data Systems”, etc.
One way to use a PUF to create a cryptographic key is as follows. First, during an enrollment phase, a challenge-response pair is created. Then, using the fuzzy extractor, helper data is created. On the device the challenge and the helper data are stored in a non-volatile memory. To derive the cryptographic key, a new response is obtained by evaluating the PUF for the challenge again. By combining the new response with the stored helper data, according to a helper data algorithm, a key is derived. The helper data ensures that the key is the same, each time it is derived.
Without a PUF, the cryptographic key may be recovered by an attacker, by mounting a physical attack on the non-volatile memory where the key is traditionally stored. For example, the attacker may open the memory and probe its content. Using a PUF makes this type of attack much harder, since opening the PUF will typically disturb the precise way in which the PUF interacts with inputs. Accordingly, information the attacker learns from his probe is not related to the interaction which was used to create the cryptographic key. This makes it harder for an attacker to find the key using a physical attack.
Unfortunately, intrusive physical attacks are not the only attack vector along which an attacker may obtain at least some information on the internal state of the PUF. So-called side channels may also leak information. A side-channel is an information source on a system related to physical phenomena occurring inside the system that may be observed from outside the system and that reveals information which, at least to some extend, is correlated with the internal operation and/or state of the system, other than its intended, observable, input-output behavior.
Power consumption, time consumption and electromagnetic radiation are examples of side-channels that are relevant to cryptographic systems. For example, the power consumption of a cryptographic system monitored while the system uses a cryptographic key may to some extend be correlated to the key. As it is of prime importance to keep the cryptographic key confidential, any leakage of information correlated with that key is problematic.
It is a problem of the prior art that a PUF-based cryptographic system reveals information on its internal operation through side-channels.